package com.leetcode.字符串;

import java.util.Scanner;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: com.leetcode.字符串
 * @Author: lei
 * @CreateTime: 2024-03-11  15:33
 * @Description: 查找两个字符串a, b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
 * 输入：abcdefghijklmnop
 * abcsafjklmnopqrstuvw
 * <p>
 * 输出：jklmnop
 * @Version: 1.0
 */
public class 查找两个字符串ab中的最长公共子串 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String a = scanner.nextLine();
            String b = scanner.nextLine();
            String shortStr = a.length() < b.length() ? a : b;
            String longStr = a.length() >= b.length() ? a : b;
            char[] shortChars = shortStr.toCharArray();
            char[] longChars = longStr.toCharArray();
            int[][] ints = new int[shortChars.length + 1][longChars.length + 1];
            int start = 0, end = 0, result = 0;
            for (int i = 0; i < shortChars.length; i++) {
                for (int j = 0; j < longChars.length; j++) {
                    if (shortChars[i] == longChars[j]) {
                        ints[i + 1][j + 1] = ints[i][j] + 1;
                        if (ints[i + 1][j + 1] > result) {
                            result = ints[i + 1][j + 1];
                            end = i + 1;
                            start = end - ints[i + 1][j + 1];
                        }
                    }
                }
            }
            System.out.println(shortStr.substring(start, end));

        }
    }
}
